const arr = [1, 5, 2, 1, 4, 9, 6]

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  let middleIndex = Math.floor(arr.length / 2)
  let middle = arr.splice(middleIndex, 1)[0]
  let left = [], right = []
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] <= middle) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }

  let res = [...quickSort(left), middle, ...quickSort(right)]
  return res
}

console.log(quickSort(arr));

